﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0182_BSTIterator : IAlgorithm
    {
        // 173. 二叉搜索树迭代器

        // 实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
        // - BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。
        //   BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
        // - boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
        // - int next()将指针向右移动，然后返回指针处的数字。
        // 注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

        // 你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

        // 提示：
        //  树中节点的数目在范围[1, 10^5] 内
        //  0 <= Node.val <= 10^6
        //  最多调用 10^5 次 hasNext 和 next 操作

        public void Test()
        {
        }

        // 算法
        public class BSTIterator
        {
            int idx;
            List<int> _list;
            public BSTIterator(TreeNode root)
            {
                idx = 0;
                _list = new List<int>();
                InorderTraversal(root, _list);
            }

            public int Next()
            {
                return _list[idx++];
            }

            public bool HasNext()
            {
                return idx < _list.Count;
            }

            private void InorderTraversal(TreeNode root, List<int> arr)
            {
                if (root == null) return;
                InorderTraversal(root.left, arr);
                arr.Add(root.val);
                InorderTraversal(root.right, arr);
            }
        }
    }
}
